1. Field of the Invention
The present invention relates to an associative memory having a function of expanding a data width to be subjected to a match retrieval to a plurality of words, or such a function that when the respective matches are detected through continuous of retrievals, a match as the whole is detected.
2. Description of the Related Art
Hitherto, there has been proposed an associative memory (a content addressable memory) having a plurality of arranged memory words each storing digital data, in which retrieval data is applied to retrieve the memory word or words storing digital data having a bit pattern which matches with a bit pattern of a whole or a predetermined part of the applied retrieval data.
FIG. 10 is a circuit block diagram of the conventional associative memory by way of example.
Referring to FIG. 10, an associative memory 10 is provided with a number of memory words 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n each consisting of a m-bit of memory cell, arranged in a transverse direction of the figure, a word being expressed with "m" bits. Further, the associative memory 10 comprises a retrieval data register 12 which is adapted to latch a word of retrieval data when it is applied thereto. A bit pattern of the whole or a predetermined part of the retrieval data latched in the retrieval data register 12 is compared with a bit pattern of the portion corresponding to the bit pattern of the latched storage data with respect to data stored in each of the memory words 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n. As a result of the comparison, if there are found any of the memory words 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n of which the bit pattern is coincident with that of the retrieval data, a match signal expressed as a logic "1" (e.g. 5 volts) will appear on the associated ones of match lines 14.sub.-- 1, 14.sub.-- 2, . . . , 14.sub.-- n which are provided in conjunction with the memory words 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n, respectively. On the other hand, a mismatch signal expressed as a logic "0" (e.g. 0 volt) will appear on the remaining ones of the match lines 14.sub.-- 1, 14.sub.-- 2, . . . , 14.sub.-- n.
The match lines 14.sub.-- 1, 14.sub.-- 2, . . . , 14.sub.-- n are connected through output lines 91, 92, . . . , n of flag registers 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n, respectively to a priority encoder 16. The signals supplied to the match lines 14.sub.-- 1, 14.sub.-- 2, . . . , 14.sub.-- n are stored in the flag registers 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n, respectively. Now, assuming that the signals "0", "1", "1", "0", . . . , "0", "0" appear on the flag registers 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n, respectively, these signals are applied to a priority encoder 16. The priority encoder 16 is so arranged to receive encode pulses (EP) and sequentially output an address signal AD corresponding to the flag register given with a higher priority among the flag registers (here, only two flag registers 15.sub.-- 2 and 15.sub.-- 3) which store the signals given by a logic "1", in accordance with a predetermined priority sequence, whenever the priority encoder 16 receives the encode pulse EP. Supposing that the higher priority is given with younger suffix, in this case, when the priority encoder 16 receives the encode pulse EP by one, the memory address associated with the flag register 15.sub.-- 2 is outputted. Thus, the priority encoder 16 outputs the address signal (AD) corresponding to the flag registers 15.sub.-- 2, which address signal AD may be passed to an address decoder 17, if necessary. The address decoder 17 decodes the received address signal AD and outputs an access signal (here logic "1" of signal) to the associated one (here a word line 18.sub.-- 2) of word lines 18.sub.-- 1, 18.sub.-- 2, . . . , 18.sub.-- n which are provided in conjunction with the memory words 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n, respectively. Thus, storage data stored in the word memory 11.sub.-- 2 associated with the word line 18.sub.-- 2 on which the access signal appears is read out to an output register 19.
Next, further application of the encode pulse EP makes it possible now to derive an address of the memory word 11.sub.-- 3 associated with the flag register 15.sub.-- 3.
As described above, according to the associative memory 10, the storage data stored in a number of memory words 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n are retrieved using the retrieval data in its entirety or a part specified, so that an address of the memory word involved in the matched data is generated, and in accordance with the necessity the whole data stored in the memory word can be read out.
With respect to the associative memory having the fundamental structure as mentioned above, there has been proposed a technology as to expansion of the data width as an object of a match retrieval into two or more words.
FIG. 11 is a block diagram of an associative memory, by way of example, provided with a data expansion function. In FIG. 11, the same parts are denoted by the same reference numbers as those of FIG. 10, and the redundant description will be omitted.
Match lines 14.sub.-- 1, 14.sub.-- 2, . . . , which are extended from the memory words 11.sub.-- 1, 11.sub.-- 2, . . . , respectively, are connected to ones of two input terminals of AND gates 20.sub.-- 1, 20.sub.-- 2, . . . , respectively. Connected to the other ones of the two input terminals of the AND gates 20.sub.-- 1, 20.sub.-- 2, . . . are output terminals of OR gates 21.sub.-- 2, 21.sub.-- 3, . . . , respectively. Ones of two input terminals of the OR gates 21.sub.-- 2, 21.sub.-- 3, . . . are connected to a first time retrieval control line 22. An OR gate associated with the AND gates 20.sub.-- 1 is omitted. The other input terminal of the AND gates 20.sub.-- 1 is directly connected to the first time retrieval control line 22.
Output terminals of the AND gates 20.sub.-- 1, 20.sub.-- 2, . . . are connected to data input terminals of first flag registers 23.sub.-- 1, 23.sub.-- 2, . . . , respectively. Output terminals of the first flag registers 23.sub.-- 1, 23.sub.-- 2, . . . are connected to output terminals of second flag registers 24.sub.-- 1, 24.sub.-- 2, . . . , respectively. Output terminals of the second flag registers 24.sub.-- 1, 24.sub.-- 2, . . . are connected to the priority encoder 16 shown in FIG. 10 (omitted in FIG. 11), respectively, and in addition to the other ones of the input terminals of the OR gates 21.sub.-- 2, 21.sub.-- 3, . . . , respectively, which correspond each to the associated one of memory words adjacent to each other downwards in FIG. 11.
Pairs of first and second flag registers 23.sub.-- 1, 24.sub.-- 1; 23.sub.-- 2, 24.sub.-- 2; . . . correspond to the flag registers 15.sub.-- 1; 15.sub.-- 2, . . . shown in FIG. 10, respectively.
Applied to both the first flag registers 23.sub.-- 1, 23.sub.-- 2, . . . and the second flag registers 24.sub.-- 1, 24.sub.-- 2, . . . are a match result latch signal S1 which appears on a match result latch control line 25, so that input data entered from the respective data input terminals are latched. In the first flag registers 23.sub.-- 1, 23.sub.-- 2, . . . , there are latched the input data involved in the time point of a rising edge a of the match result latch signal S1. On the other hand, in the second flag registers 24.sub.-- 1, 24.sub.-- 2, . . . , there are latched the input data involved in the time point of a trailing edge b of the match result latch signal S1.
In the associative memory arranged as mentioned above, a match retrieval is performed in accordance with a manner as described below. It is now assumed, as shown in the FIG. 11, that the memory words 11.sub.-- 1, 11.sub.-- 2, 11.sub.-- 3, 11.sub.-- 4, 11.sub.-- 5, 11.sub.-- 6, . . . store retrieval data A, B, C, D, C, F, . . . respectively.
To retrieve solely individual retrieval data, a first time retrieval timing signal S2 is supplied to the first time retrieval control line 22, when the retrieval is performed through inputting the retrieval data REF-DATA. Assuming that data "B" is inputted as the retrieval data REF-DATA, a logic "1" of match signal appears on the match line 14.sub.-- 2 associated with the memory word 11.sub.-- 2 in which data "B" has been stored, and is supplied to the AND gate 20-2. Simultaneously, the first time retrieval timing signal S2 is supplied via the first time retrieval control line 22 through the OR gate 21.sub.-- 2 to the AND gate 20.sub.-- 2. As a result, the AND gate 20.sub.-- 2 produces a logic "1" of signal. On the other hand, since logic "0" of signals appear on the other match lines 14.sub.-- 1, 14.sub.-- 3, 14.sub.-- 4, . . . , respectively, the associated AND gates 20-1, 20.sub.-- 3, 20.sub.-- 4, . . . produce logic "0" of signals, respectively.
The logic "1" of signal outputted from the AND gate 20.sub.-- 2 is latched by the first flag register 23.sub.-- 2 in timing of the rise-up edge a of the match result latch signal S1 appearing on the match result latch control line 25, and then latched by the second flag register 24.sub.-- 2 in timing of the subsequent trailing edge b of the match result latch signal S1.
On the other hand, logic "0" of signals are latched by the other first flag registers 23.sub.-- 1, 23.sub.-- 3, 23.sub.-- 4, . . . in the same timing as the logic "1" of signal is latched by the first flag register 23.sub.-- 2, and logic "0" of signals are latched by the other second flag registers 24.sub.-- 1, 24.sub.-- 3, 24.sub.-- 4, . . . in the same timing as the logic "1" of signal is latched by the second flag register 24.sub.-- 2.
In this manner, signals expressed by logic "0", "1", "0", . . . , which are latched by the second flag registers 24.sub.-- 1, 24.sub.-- 2, 24.sub.-- 3, . . . , respectively, are supplied to the priority encoder 16 as shown in FIG. 10 to generate an address signal AD of the memory word 11.sub.-- 2.
Next, there will be explained such a case where a retrieval involved in expansion of the data width is performed. Here, a case where two-word data consisting of data "B" and data "C" is retrieved, by way of example, will be explained.
In the same manner as the above-mentioned case, first, a retrieval of the data "B" is performed. As a result, signals expressed by logic "1" are latched by the first flag register 23.sub.-- 2 and the second flag register 24.sub.-- 2, respectively, which are associated with the memory word 11.sub.-- 2. Next, the data "C" is inputted as the retrieval data REF-DATA for retrieval. At that time, the time retrieval timing signal S2 is not supplied to the first time retrieval control line 22, and the first time retrieval control line 22 is kept logic "0". Performing the retrieval through inputting the data "C" as the retrieval data REF-DATA will induce match signals expressed by logic "1" on the match lines 14.sub.-- 3 and 14.sub.-- 5 which are associated with the memory words 11.sub.-- 3 and 11.sub.-- 5, respectively. Since the logic "1" of signal latched by the second flag register 24.sub.-- 2 has been supplied to the OR gate 21.sub.-- 3, the match signal appearing on the match line 14.sub.-- 3 is passed via the AND gate 20.sub.-- 3 to the first and second flag registers 23.sub.-- 3 and 24.sub.-- 3, so that a signal expressed by logic "1" representative of a match is latched by the first and second flag registers 23.sub.-- 3 and 24.sub.-- 3. On the other hand, since the logic "0" of signal latched by the second flag register 24.sub.-- 4 has been supplied to the OR gate 21.sub.-- 5, the match signal appearing on the match line 14.sub.-- 5 is inhibited by the AND gate 20.sub.-- 5, so that a signal expressed by logic "0" representative of a mismatch is latched by the first and second flag registers 23.sub.-- 5 and 24.sub.-- 5. In this manner, there is carried out a match retrieval for two-word data consisting of a pair of data "B" and data "C". Likewise, a match retrieval for three-word data or more word data may be implemented.
While the associative memory shown in FIG. 11 is provided with a data width expansion function, it is necessary for data to be expanded to two-word, three-word and so on to be stored in mutually adjacent memory words in a predetermined order, and thus it is impossible to perform a match retrieval in combination of plural data, in a case where plural data to be retrieved are stored in the reversed order, for example, in sequence of data "C" and data "B", or in a case where they are stored in mutually distant memory words.
FIG. 12 shows a data structure which needs the retrieval as mentioned above. In FIG. 12, there is shown a data structure in which each data group is constituted of a set of data consisting of four data appended with attributes I, II, III and IV, respectively. Now, in order to clarify a concept of the data groups and the attributes, an example will be given. For instance, each of data groups assigned with the group numbers 1, 2, 3, 4 . . . is associated with data involved in an individual, attribute I denotes a name of the associated person, attribute II denotes the date of birth of the associated person, attribute III denotes the address of the associated person, . . . and so on.
In case of retrieval under storage of data groups, each consisting of a plurality of data appended with the attributes I, II, III and IV as mentioned above, into an associative memory, for instance, when data of the group number 1 is retrieved, the following various situations may occur by way of example. As one situation, there is considered such a case that the retrieval of data "A" and the retrieval of data "B" are performed in the named order and then the remaining data "C" and "D" involved in the matched data group are read. Further, sometimes it is desired that for example, the retrieval of data "A" and the retrieval of "D" are performed and then the remaining data "B" and "C" are read. Alternatively, sometimes it is desired that first the retrieval of data "B" is performed and then the retrieval of "A" is performed.
However, it is impossible for the above-mentioned associative memory (refer to FIG. 11) having the word width expansion function to perform those retrievals as mentioned above. Further, according to the above-mentioned associative memory, when the retrieval of data "A" and data "B " is performed, it is impossible to distinguish between a pair of data "A" appended with attribute I and data "B" appended with attribute II each associated with the group number 1 shown in FIG. 12 and a pair of data "A" appended with attribute II and data "B" appended with attribute III each associated with the group number 4 shown in FIG. 12. Specifically, assuming that attribute I stands for "name" and attribute II "one's date of birth", when it is desired on the basis of information as to those attributes I and II to detect information as to attributes III and IV of a specified individual who matches the attributes I and II, it may happen that a match is detected through even a pair of attributes II and III.
In order to solve the problems as mentioned above, there has been proposed in Japanese Patent Application No. 248121/1993 a new associative memory which makes it possible to perform also a retrieval involved in a discontinuous attribute.
However, this associative memory involves such a problem that with respect to data in a series of data groups, for example, a retrieval is performed for each attribute, a management of addresses for a match or a mismatch is complicated and then it is complicated to treat memory word groups each storing a data group as units.